#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
vector<int>index;
vector<int> tmp;
vector<int> ret;
vector<int> index2;
void merge(vector<int>& nums, int l, int r)
{
    if (l >= r)return;
    int mid = l + (r - l) / 2;
    merge(nums, l, mid);
    merge(nums, mid + 1, r);
    int cur1 = l, cur2 = mid + 1;
    int j = 0;
    while (cur1 <= mid && cur2 <= r)
    {
        if (nums[cur1] > nums[cur2])
        {
            ret[index[cur1]] += r - cur2 + 1;
            index2[j++] = index[cur1];
            tmp.push_back(nums[cur1++]);
        }
        else
        {
            index2[j++] = index[cur2];
            tmp.push_back(nums[cur2++]);
        }
    }
    while (cur1 <= mid)tmp.push_back(nums[cur1++]);
    while (cur2 <= r)tmp.push_back(nums[cur2++]);
    for (int i = 0; i < tmp.size(); i++)
    {
        nums[i + l] = tmp[i];
        index[i + l] = index2[i];
    }
}
vector<int> countSmaller(vector<int>& nums)
{
    index.clear();
    index2.clear();
    int n = nums.size();
    index.resize(n);
    index2.resize(n);
    for (int i = 0; i < n; i++)
        index[i] = i;
    ret.clear();
    ret.resize(n);
    merge(nums, 0, n - 1);
    return ret;
}
int main()
{
    vector<int> nums={5, 2, 6, 1};
    countSmaller(nums);
    return 0;
}